/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class SetIntersectionSizeAtLeastTwo {
	public int intersectionSizeTwo(int[][] intervals) {
		Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : (a[1] - b[1]));
		int n = intervals.length;
		int ans = 0;
		int lr = -1;
		int ll = -1;
		for (int i = 0; i < n; i++) {
			if (intervals[i][0] > lr) {// 如果起始位置>lr,则要两个点
				ans += 2;
				lr = intervals[i][1];
				ll = lr - 1;
				System.out.println(ll);
				System.out.println(lr);
			} else if (intervals[i][0] > ll) {
				ans++;
				ll = lr;
				lr = intervals[i][1];
				System.out.println(lr);
			}
		}
		return ans;
	}

	/**
	 * 221 ms
	 * 
	 * @param intervals
	 * @return
	 */
	public int intersectionSizeTwoxx(int[][] intervals) {
		Arrays.sort(intervals, (a, b) -> (a[1] - b[1]));
		int n = intervals.length;
		int[] status = new int[n];
		int ans = 0;
		int lr = -1;
		int ll = -1;
		for (int i = 0; i < n; i++) {
			if (status[i] == 2) {
				continue;
			} else if (status[i] == 1) {
				ans++;
				ll = lr;
				lr = intervals[i][1];
				System.out.println(lr);
			} else if (status[i] == 0) {
				ans += 2;
				lr = intervals[i][1];
				ll = lr - 1;
				System.out.println(ll);
				System.out.println(lr);
			}
			for (int j = i + 1; j < n; j++) {
				if (status[j] == 2) {
					continue;
				}
				if (intervals[j][0] <= ll) {
					status[j] = 2;
				} else if (intervals[j][0] <= lr) {
					status[j] = 1;
				}
			}
		}
		return ans;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] intervals = { { 1, 5 }, { 4, 5 }, { 5, 9 }, { 7, 9 }, { 9, 10 } };
		System.out.println(new SetIntersectionSizeAtLeastTwo().intersectionSizeTwo(intervals));
	}

}
